package J20250121_Dynamic;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description: 动态规划47——50
 * User: 王圆豪
 * Date: 2025-02-07
 * Time: 18:31
 */
public class Solution7 {
    //两个字符串的最⼩ASCLL删除和（medium）——https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/
    public int minimumDeleteSum(String ss1, String ss2) {
        int m = ss1.length(), n = ss2.length();
        char[] s1 = ss1.toCharArray();
        char[] s2 = ss2.toCharArray();
        int[][] dp = new int[m+1][n+1];
        for(int i = 1; i <= n; i++) dp[0][i] = dp[0][i-1] + s2[i-1];
        for(int i = 1; i <= m; i++) dp[i][0] = dp[i-1][0] + s1[i-1];
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(s1[i-1] == s2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i][j-1]+s2[j-1],dp[i-1][j]+s1[i-1]);
                }
            }
        }
        return dp[m][n];
    }

    //最⻓重复⼦数组——https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m+1][n+1];
        int ret = 0;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(nums1[i-1] == nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                ret = Math.max(ret, dp[i][j]);
            }
        }
        return ret;
    }

    //01背包——https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e?tpId=230&tqId=2032484&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int V = sc.nextInt();
        int[] v = new int[n];
        int[] w = new int[n];
        for(int i = 0; i < n; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        int ret1 = bag1(v, w, n, V);
        int ret2 = bag2(v, w, n, V);
        System.out.println(ret1);
        System.out.println(ret2);
    }

    public static int bag1(int[] v, int[] w, int n, int V){
        int[] dp = new int[V+1];
        for(int i = 0; i < n; i++){
            for(int j = V; j >= v[i]; j--){
                dp[j] = Math.max(dp[j], dp[j-v[i]]+w[i]);
            }
        }
        return dp[V];
    }

    public static int bag2(int[] v, int[] w, int n, int V){
        int[] dp = new int[V+1];
        for(int i = 1; i <= V; i++) dp[i] = -1;
        for(int i = 0; i < n; i++){
            for(int j = V; j >= v[i]; j--){
                if(dp[j-v[i]] != -1) dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
            }
        }
        return dp[V] == -1 ? 0 : dp[V];
    }

    //分割等和⼦集——https://leetcode.cn/problems/partition-equal-subset-sum/
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int a : nums) sum += a;
        if(sum % 2 != 0) return false;
        sum /= 2;
        int n = nums.length;
        boolean[] dp = new boolean[sum+1];
        for(int i = 0; i <= n; i++) dp[0] = true;
        for(int i = 1; i <= n; i++){
            for(int j = sum; j >= nums[i-1]; j--){
                dp[j] = dp[j] || dp[j-nums[i-1]];
            }
        }
        return dp[sum];
    }
}
